#include <cstdio>
#include <vector>
#include <algorithm>

#include <utility>
#include "BigInt.h"

void BigInt::print() const {
    
    if (this->flag == NEGATIVE) {
        printf("-");
    }

    for (auto it = v.rbegin(); it != v.rend(); it++) {
        printf("%d", *it);
    }
    printf("\n");
}


BigInt BigInt::Div(const BigInt &div){

        if (div.isZero()) {
            printf("divition can't be 0\n");
            return BigInt(0);
        }
        if ( isZero() || div.AbsCompareTo(*this) > 0) {
            return BigInt(0);
        }

        int f_flag = isSameFlag(div) ? POSITIVE : NEGATIVE;


        BigInt res(0);
        while (div.AbsCompareTo(*this) <= 0) {
            BigInt rb(div);

            int pos = 0;
            while (rb.AbsCompareTo(*this) <= 0) {
                rb.LeftShift();
                pos++;
            }
            rb.RightShift();
            pos--;


           // rb.print();
            int cnt = 0;
            while (rb.AbsCompareTo(*this) <= 0) {
                *this = AbsMinus(rb);
                //this->print();
                cnt++;
            }
            BigInt tmpRes(cnt);
            tmpRes.LeftShift(pos);

            res.Add(tmpRes);            
        }
        
        res.flag = f_flag;
        this->flag = f_flag;
        if (isZero()) {
            this->flag = ZERO;
        }

        return res;
}

    

const BigInt& BigInt::Multiply(const BigInt &mul)
{

    this->flag *= mul.flag;
    if (this->flag == ZERO) {
        this->setZero();
        return *this;
    }
    auto cnt_bits = mul.getLen() + this->getLen() + 1;
    BigInt res( cnt_bits, 0);
    res.flag = this->flag;
        
    auto mlen = mul.v.size();
    auto  len = v.size();
    for (std::size_t i = 0;i < mlen; i++) {
        for (std::size_t j = 0; j < len; j++) {
            res.v[i + j] += this->v[j] * mul.v[i];
        }
    }

    int carry = 0;
    for (std::size_t i = 0;i < cnt_bits; i++) {
        int tmp = carry + res.v[i];
        carry = tmp / BASE;
        res.v[i] = tmp % BASE;
    }
    
    while (cnt_bits > 1 && res.v[cnt_bits - 1] == 0) {
        cnt_bits--;
        res.v.pop_back();
    }
    *this = res;


    return (*this);
}

BigInt::BigInt(int cnt, int v):v(cnt, v){

}
template<typename T>
BigInt::BigInt(T a) {
    if (a == 0) {
        setZero();
    }
    else {
        flag = POSITIVE;
        if (a < 0) {
            flag = NEGATIVE;
            a = -a;
        }
        while (a) {
            v.push_back(a % 10);
            a /= 10;
        }
    }
}
const BigInt& BigInt::Add(const BigInt& b)
{

    int f = flag;
    if (!isSameFlag(b)) {

        int cmp = AbsCompareTo(b);

        if (0 == cmp) {
            setZero();
            f = ZERO;
        }
        else if (cmp == 1) {
            *this = AbsMinus(b);
        }
        else {
            *this = b.AbsMinus(*this);
            f  = b.flag;
        }
    }
    else {
        if (flag == ZERO)
            f = b.flag;
        *this = AbsAdd(b);
    }
    this->flag = f;

    return *this;
}


BigInt BigInt::AbsAdd(const BigInt& b) const
{
    int carry = 0;
    auto len = v.size();
    auto blen = b.v.size(); 

    BigInt tv(*this);
    auto cnt_bits = std::max(blen, len);

    for (int i = 0;i < cnt_bits;i++) {
        int tmp = carry;
        if (i < blen)
            tmp += b.v[i];
        if (i < len)
            tmp += tv.v[i];
        else {
            tv.v.push_back(0);
            len++;
        }

        carry = tmp / BASE;
        tv.v[i]  = tmp % BASE;
    }
    if (carry) {
        tv.v.push_back(carry);
    }
    return tv;
}
const BigInt& BigInt::Multiply(int p) 
{
    if (p == 0) {
        setZero();
    }
    else {
        this->Multiply(BigInt(p));
    }
    return *this;
}
const BigInt& BigInt::Minus(const BigInt &n) {

    if (n.equal(*this)) {
        setZero();
        return *this;
    }

    int f1 = this->flag;
    int f2 = n.flag;

    int f = f1;
    if ( !isSameFlag(n)) {
        *this = AbsAdd(n);

        //printf("here is!!!\n");
        if (f == ZERO)
            f = -f2;
    }
    else {

        //printf("why here ?\n");
        int cmp = AbsCompareTo(n);
        if ( cmp < 0) {
            *this = n.AbsMinus(*this);
            f = -f2;
        }
        else {
            *this = AbsMinus(n);
        }
    }
    flag = f;

    return *this;
}

BigInt BigInt::AbsMinus(const BigInt &n) const {
    std::size_t len = v.size();
    std::size_t nvlen = n.v.size();
    int carry = 0;
    BigInt tv(*this);


    for (int i = 0;i < len; i++) {
        tv.v[i] += carry;
        if (i < nvlen)
           tv.v[i] -= n.v[i];

        carry = 0;
        if (tv.v[i] < 0) {
            carry = -1;
            tv.v[i] += BASE;
        }
    }

    while (len > 1 && tv.v[len - 1] == 0) {
        len--;
        tv.v.pop_back();
    }
    return tv;
}

BigInt::BigInt(const std::string& str) {
    if (! assign(str) ) {
        setZero();
    }
}
BigInt::BigInt(const char *str) {
    if ( !assign(str) ) {
        setZero();
    }
}

bool BigInt::assign(const std::string& str)
{
    if (BigInt::isLeagalBigIntStr(str)) {
        
        int sz = static_cast<int>( str.size() );
        int p  = 0;
        if ( str[0] == '-') {
            this->flag = NEGATIVE;
            p++;
        }
        else if ( str[0] == '0') {
            this->flag = ZERO;
        }
        else {
            this->flag = POSITIVE;
        }

        this->v.clear();

        for (int i = sz - 1; i >= p; i-- ) {
            v.push_back(str[i] - '0');
        }

        return true;
    }
    else {
        return false;
    }
}


bool BigInt::assign(const char *str)
{
    std::string s(str);

    return assign(s);
}

bool BigInt::isLeagalBigIntStr(const std::string& str)
{
    int sz = static_cast<int>( str.size());

    if (0 == sz)
        return false;

    int p = 0;
    if (str[p] == '-') {
        p++;

        //  just a '-'
        if ( p == sz )
            return false;
        
        // process: -0
        if (sz >  1 && str[p] == '0')
            return false;
    }


    // process: 023424
    if (str[p] == '0' && p + 1 < sz )
        return false;


    for ( ; p < sz; p++) {
        if(!isdigit(str[p]))
            return false;
    }

    return true;
}
